package com.LeeCode;

import java.util.Arrays;

/**
 * 范围内整数的最大得分
 */

public class Code3281 {
    public static void main(String[] args) {
        int[] start = {1000000000, 0};
        int d = 1000000000;
        System.out.println(new Code3281().maxPossibleScore(start, d));
    }

    public int maxPossibleScore(int[] start, int d) {
        Arrays.sort(start);
        int n = start.length, left = 0, right = start[n - 1] + d - start[0] + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(start, d, mid))
                left = mid;
            else
                right = mid;
        }
        return left;
    }

    private boolean check(int[] start, int d, int min) {
        long pre = start[0]; // 注意数据溢出问题
        for (int i = 1; i < start.length; i++) {
            long low = start[i], high = low + d;
            pre = Math.max(low, pre + min);
            if (pre > high)
                return false;
        }

        return true;
    }
}
